When processing signals in wireless communication networks, such as a 3G Long Term Evolution (LTE) network (one of which is known as Evolved Universal Terrestrial Radio Access—E-UTRA, developed by the 3rd Generation Partnership Project—3GPP), it is often necessary to carry out a Discrete Fourier Transform (DFT) on an input signal. The DFT is used to transform the input signal from the time domain to the frequency domain. An inverse-DFT is used to transform an input signal from the frequency domain to the time domain.
A Discrete Fourier Transform engine in a Field Programmable Gate Array (FPGA) receives m-length complex samples at its input and transforms them to m-length complex samples at its output. The input samples are assumed to be in a normal order, so, for a time-to-frequency transformation, the first time sample will be t0, the second sample will be t1, the third sample will be t2, and so on. To be useful, the output samples (denoted bin0, bin1, . . . ) should also be in a normal order, so bin0 first, bin1 second, bin2 third and so on.
However, in performing the DFT efficiently, the DFT engine operates on the input samples in order, but the output samples are mixed up and disordered. The same applies when an inverse-DFT is performed on an ordered set of input samples.
Thus, the output samples must be reordered before they can be used by subsequent components. There is therefore a need for an algorithm that can reorder the output samples.